package Leetcode第一期;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author : K k
 * @date : 10:00 2020/9/11
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 *
 *  
 *
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 *
 */
public class 二叉树中和为某一值的路径_34 {
    private List<List<Integer>> lists=new ArrayList<>();
    private Deque<Integer> path=new ArrayDeque<>();

    //思路 类似组合总和II leetcode216题
    //回溯 深度优先算法
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null) {return lists;}

        dfsSolver(root,sum);
        return lists;
    }

    private void dfsSolver(TreeNode root, int sum) {
        //若大于则失败
        if ( root==null){return;}
        //若符合条件则加入
        path.addLast(root.val);
        //需要的路径是根节点到叶子节点
        if (root.val==sum && root.left==null &&root.right==null){
            lists.add(new ArrayList<>(path));
        }

        if (root.left!=null){
            dfsSolver(root.left,sum-root.val);
        }
        if (root.right!=null){
            dfsSolver(root.right,sum-root.val);
        }
        path.removeLast();
    }

    int maxd=0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxd;
    }
    public int depth(TreeNode node){
        if(node==null){
            return 0;
        }
        int Left = depth(node.left);
        int Right = depth(node.right);
        maxd=Math.max(Left+Right,maxd);//将每个节点最大直径(左子树深度+右子树深度)当前最大值比较并取大者
        return Math.max(Left,Right)+1;//返回节点深度
    }

}
